#include<stdio.h>
#include<stdlib.h>

void swap(int &a,int &b){
    int temp=a;
    a=b;
    b=temp;
}
/*
*维护大顶堆（升序）
*param i待维护节点下标
*/
void heapify(int arr[],int n,int i){
    int largest=i;
    int lson=i*2+1;
    int rson=i*2+2;
    if(lson<n&&arr[largest]<arr[lson])
        largest=lson;
    if(rson<n&&arr[largest]<arr[rson])
        largest=rson;
    if(largest!=i)
    {
        swap(arr[largest],arr[i]);
        heapify(arr,n,largest);//largest是换过后可能需要维护的子树的根节点  
    }
}
void heap_sort(int arr[],int n){
    int i;
    //建堆
    for(i=n/2-1;i>=0;i--){
        heapify(arr,n,i);
    }
    //此时数组仍然时无序的
    //排序，交换堆顶和最后一个叶子节点交换，从后往前排序每次排出一个最大的。重新维护新的堆
    for(i=n-1;i>0;i--){
        swap(arr[i],arr[0]);
        heapify(arr,i,0);
    }
}
int main(int arc,char const *argv[]){
    int arr[6]={10,20,30,14,15,40};
    heap_sort(arr,6);
    for(int i=0;i<6;i++){
        printf("%d ",arr[i]);
    }
    return 0;
}